import java.util.*;

public class Practices {
    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static double max(double a, double b, double c) {
        return Math.max(Math.max(a, b), c);
    }

    public static int fun(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;
        return fun(n - 1) + fun(n - 2);
    }

    public static int count(int n) {
        int count = 0;
        while (n != 0) {
            count += n % 10;
            n /= 10;
        }
        return count;
    }

    public static void myPrint(int n) {
        if (n / 10 != 0) myPrint(n / 10);
        System.out.print(n % 10);
    }

    public static int addAll(int n) {
        if (n == 1) return n;
        return n * addAll(n - 1);
    }

    public static double avg(int[] arr) {
        double avg = 0;
        for (int s : arr) {
            avg += s;
        }
        System.out.println("一共" + arr.length + "个元素,合为: " + avg);
        return avg / arr.length;
    }

    public static void transFrom(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * 2;
        }
    }

    public static void printArray(int[] arr) {
        for (int s : arr) {
            System.out.print(s + " ");
        }
    }

    public static void toString(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.print(arr[arr.length - 1] + "]");
    }

    public static void find(int[] arr, int n) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int tmp = (left + right) / 2;
            if (arr[tmp] > n) {
                right = tmp - 1;
            } else if (arr[tmp] < n) {
                left = tmp + 1;
            } else {
                System.out.println("找到了,下标为" + tmp);
                return;
            }
        }
        System.out.println("不存在");
    }

    public static boolean isOrder(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) {
                return false;
            }
        }
        return true;
    }

    public static void asc(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            Boolean flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = 0;
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }

    public static int firstOne(int[] arr) {
        int tmp = arr[0];
        for (int i = 1; i < arr.length; i++) {
            tmp = tmp ^ arr[i];
        }
        return tmp;
    }

    static class Test {
        @Override
        public String toString() {
            return "Test{}";
        }
    }

    static class Node {
        int val;
        Node perv;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    static class MyLinkedList1 {
        Node head;

        public void add(int val) {
            Node node = new Node(val);
            if (head == null) {
                head = node;
                return;
            }
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
            node.perv = cur;
        }

        public void delete(int val) {
            Node cur = head;
            if (cur == null) {
                System.out.println("链表为空");
                return;
            }
            while (cur.val == val) {
                if (cur.next == null) {
                    head = null;
                    return;
                }
                cur.next.perv = null;
                head = head.next;
                cur = head;
                System.out.println("已删除");
            }
            while (cur != null) {
                while (cur.val != val && cur.next != null) {
                    cur = cur.next;
                }
                if (cur.val == val && cur.next != null) {
                    cur.perv.next = cur.next;
                    cur.next.perv = cur.perv;
                    System.out.println("已删除");
                    cur = cur.next;
                } else if (cur.val == val) {
                    cur.perv.next = null;
                    System.out.println("已删除");
                    break;
                } else {
                    break;
                }
            }
            System.out.println("全部删除");
        }
    }

    static class NodeOne {
        int val;
        NodeOne next;

        public NodeOne(int val) {
            this.val = val;
        }
    }

    static class OneLinked {
        NodeOne head;

        public void add(int val) {
            NodeOne nodeOne = new NodeOne(val);
            if (head == null) {
                head = nodeOne;
                return;
            }
            NodeOne cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = nodeOne;
        }

        public void addAll(NodeOne tmp) {
            NodeOne cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = tmp;
        }

        public void reverse() {
            if (head == null || head.next == null) return;
            NodeOne one = head;
            NodeOne two = head.next;
            NodeOne three = head.next.next;
            two.next = one;
            one.next = null;
            while (three != null) {
                one = two;
                two = three;
                three = three.next;
                two.next = one;
            }
            head = two;
        }

        public void reverseIndex(int x) {
            if (x == 0) {
                reverse();
                return;
            }
            NodeOne cur = head;
            for (int i = 0; i < x - 1; i++) {
                cur = cur.next;
            }
            if (cur.next == null || cur.next.next == null) return;
            NodeOne one = cur.next;
            NodeOne two = cur.next.next;
            NodeOne three = cur.next.next.next;
            two.next = one;
            one.next = null;
            while (three != null) {
                one = two;
                two = three;
                three = three.next;
                two.next = one;
            }
            cur.next = two;
        }

        public NodeOne middle() {
            NodeOne slow = head;
            NodeOne fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        public NodeOne backwards(int k) {
            NodeOne slow = head;
            NodeOne fast = head;
            for (int i = 0; i < k - 1; i++) {
                fast = fast.next;
            }
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

        public NodeOne remove() {
            if (head == null) return null;
            NodeOne tmp = head;
            head = head.next;
            tmp.next = null;
            return tmp;
        }

        public NodeOne merge(OneLinked oneLinked1, OneLinked oneLinked2) {
            if (oneLinked1.head == null) {
                return oneLinked2.head;
            }
            if (oneLinked2.head == null) {
                return oneLinked1.head;
            }
            NodeOne tmp1 = oneLinked1.remove();
            NodeOne tmp2 = oneLinked2.remove();
            while (tmp1 != null && tmp2 != null) {
                if (tmp1.val > tmp2.val) {
                    add(tmp2.val);
                    tmp2 = oneLinked2.remove();
                } else {
                    add(tmp1.val);
                    tmp1 = oneLinked1.remove();
                }
            }
            if (tmp1 == null) {
                addAll(tmp2);
                addAll(oneLinked2.head);
                oneLinked2.head = null;
            }
            if (tmp2 == null) {
                addAll(tmp1);
                addAll(oneLinked1.head);
                oneLinked1.head = null;
            }
            return head;
        }

        public boolean isReturn() {
            if (head == null || head.next == null) return true;
            Stack<Integer> stack = new Stack<>();
            int size = 0;
            NodeOne cur = head;
            while (cur != null) {
                stack.push(cur.val);
                size++;
                cur = cur.next;
            }
            cur = head;
            for (int i = 0; i < size / 2; i++) {
                if (cur.val != stack.pop()) {
                    return false;
                }
                cur = cur.next;
            }
            return true;
        }
    }

    public static class MyLinkedList {
        class MyNode {
            int val;
            MyNode perv;
            MyNode next;

            public MyNode(int val) {
                this.val = val;
            }
        }

        public MyNode head;
        public int size;

        public void add(int val) {
            MyNode myNode = new MyNode(val);
            if (head == null) {
                head = myNode;
                size++;
                return;
            }
            MyNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = myNode;
            myNode.perv = cur;
            size++;
        }

        public void addAll(MyNode tmp) {
            if (head == null) {
                head = tmp;
            }
            MyNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = tmp;
            tmp.perv = cur;
            int count = 0;
            while (tmp != null) {
                count++;
                tmp = tmp.next;
            }
            size += count;
        }

        public MyNode deleteFirst() {
            if (head == null) {
                return null;
            }
            MyNode cur = head;
            head = head.next;
            head.perv = null;
            cur.next = null;
            size--;
            return cur;
        }

        public MyNode deleteLast() {
            if (head == null) {
                return null;
            }
            MyNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.perv.next = null;
            cur.perv = null;
            size--;
            return cur;
        }

        public void deleteMyNode(MyNode myNode) {
            if (myNode.perv == null && myNode.next == null) return;
            if (myNode.perv == null) {
                deleteFirst();
                return;
            }
            if (myNode.next == null) {
                deleteLast();
                return;
            }
            myNode.perv.next = myNode.next;
            myNode.next.perv = myNode.perv;
            myNode.next = null;
            myNode.perv = null;
            size--;
        }

        public MyNode delete(int index) {
            if (index < 0 || index > size - 1) return null;
            if (index == 0) {
                return deleteFirst();
            }
            if (index == size - 1) {
                return deleteLast();
            }
            MyNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.perv.next = cur.next;
            cur.next.perv = cur.perv;
            cur.next = null;
            cur.perv = null;
            size--;
            return cur;
        }

        public int queryIndex(int index) {
            if (index < 0 || index > size - 1) {
                System.out.println("下标位置不合适");
                return -1;
            }
            MyNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }

        public int queryVal(int val) {
            if (head == null) {
                System.out.println("链表为空");
            }
            int tmp = 0;
            MyNode cur = head;
            while (cur != null) {
                if (cur.val == val) {
                    return tmp;
                }
                cur = cur.next;
                tmp++;
            }
            System.out.println("链表中不存在该值");
            return -1;
        }

        public void updateIndex(int index, int val) {
            if (index < 0 || index > size - 1) {
                System.out.println("下标位置不合适");
            }
            MyNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.val = val;
        }

        public void updateVal(int oldVal, int newVal) {
            if (head == null) {
                System.out.println("链表为空");
            }
            MyNode cur = head;
            while (cur != null) {
                if (cur.val == oldVal) {
                    cur.val = newVal;
                    return;
                }
                cur = cur.next;
            }
            System.out.println("链表中不存在该值");
        }

        public void create() {
            MyNode a = new MyNode(2);
            MyNode b = new MyNode(5);
            MyNode c = new MyNode(3);
            MyNode d = new MyNode(2);
            a.next = b;
            b.perv = a;
            b.next = c;
            c.perv = b;
            c.next = d;
            d.perv = c;
            size = 4;
            head = a;
        }

        public MyNode returnIndex() {
            MyNode slow = head;
            MyNode fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    slow = head;
                    while (slow != fast) {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            System.out.println("无环");
            return null;
        }

        public MyNode returnSameMyNode(MyLinkedList myLinkedList, MyLinkedList myLinkedList1) {
            if (myLinkedList.head == null || myLinkedList1.head == null) return null;
            int count = 1;
            MyNode cur = myLinkedList.head;
            while (cur.next != null) {
                cur = cur.next;
                count++;
            }
            int count1 = 1;
            MyNode cur1 = myLinkedList1.head;
            while (cur1.next != null) {
                cur1 = cur1.next;
                count1++;
            }
            int dValue = count > count1 ? count - count1 : count1 - count;
            cur = myLinkedList.head;
            cur1 = myLinkedList1.head;
            if (count > count1) {
                for (int i = 0; i < dValue; i++) {
                    cur = cur.next;
                }
            } else {
                for (int i = 0; i < dValue; i++) {
                    cur1 = cur1.next;
                }
            }
            while (cur != null) {
                if (cur == cur1) {
                    return cur;
                }
                cur = cur.next;
                cur1 = cur1.next;
            }
            return null;
        }

        public void subVal(int val) {
            MyNode cur = head;
            int count = 0;
            for (int i = 0; i < size; i++) {
                if (cur.val >= val) {
                    MyNode tmp = cur.next;
                    addAll(delete(count));
                    cur = tmp;
                } else {
                    cur = cur.next;
                    count++;
                }
            }
        }

        public MyNode removeRepeat() {
            ArrayList<Integer> list = new ArrayList<>();
            MyNode cur = head;
            int length = size;
            for (int i = 0; i < length; i++) {
                if (!list.contains(cur.val)) {
                    list.add(cur.val);
                    cur = cur.next;
                } else {
                    MyNode tmp = cur.next;
                    deleteMyNode(cur);
                    cur = tmp;
                }
            }
            return head;
        }
    }

    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        if (grid == null) {
            return null;
        }
        int m = grid.length;
        if (m == 0) {
            return null;
        }
        int n = grid[0].length;
        if (n == 0) {
            return null;
        }
        for (int i = 0; i < k; i++) {
            int[][] arr = new int[m][n];
            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (j == m - 1 && l == n - 1) {
                        arr[0][0] = grid[j][l];
                    } else if (l == n - 1) {
                        arr[j + 1][0] = grid[j][l];
                    } else {
                        arr[j][l + 1] = grid[j][l];
                    }
                }
            }
            grid = arr;
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int[] ints : grid) {
            List<Integer> list1 = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                list1.add(ints[j]);
            }
            list.add(list1);
        }
        return list;
    }

    public List<List<Integer>> shiftGridPlus(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add(0);
            }
            list.add(row);
        }
        for (int i = 0; i < m * n; i++) {
            int index = (i + k) % (m * n);
            list.get(index / n).set(index%n,grid[i/n][i%n]);
        }
        return list;
    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int tmp1;
        int tmp2;
        for (String s:tokens) {
            switch (s){
                case "+":
                    tmp1 = stack.pop();
                    tmp2 = stack.pop();
                    stack.push(tmp2+tmp1);
                    break;
                case "-":
                    tmp1 = stack.pop();
                    tmp2 = stack.pop();
                    stack.push(tmp2-tmp1);
                    break;
                case "*":
                    tmp1 = stack.pop();
                    tmp2 = stack.pop();
                    stack.push(tmp2*tmp1);
                    break;
                case "/":
                    tmp1 = stack.pop();
                    tmp2 = stack.pop();
                    stack.push(tmp2/tmp1);
                    break;
                default:
                    stack.push(Integer.parseInt(s));
                    break;
            }
        }
        return stack.pop();
    }
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stack1 = new Stack<>();
        for (int i = popA.length - 1; i >= 0; i--) {
            stack1.push(popA[i]);
        }
        for (int a:pushA) {
            if (a == stack1.peek()){
                stack1.pop();
                while (!stack.isEmpty() && stack.peek().equals(stack1.peek())){
                    stack.pop();
                    stack1.pop();
                }
            }else {
                stack.push(a);
            }
        }
        if (stack1.isEmpty()){
            return true;
        }
        return false;
    }
    public boolean IsPopOrderPlus(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int tmp = 0;
        for (int j : pushA) {
            if (j != popA[tmp]) {
                stack.push(j);
            } else {
                tmp++;
                while (tmp < popA.length) {
                    if (!stack.isEmpty() && stack.peek() == popA[tmp]) {
                        stack.pop();
                        tmp ++;
                    }else {
                        break;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
    public String build(String s){
        StringBuilder s1 = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch1 = s.charAt(i);
            if (ch1 != '#'){
                s1.append(s);
            }else {
                if (s1.length() != 0){
                    s1.deleteCharAt(s1.length()-1);
                }
            }
        }
        return s1.toString();
    }
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));
    }
    static class RecentCounter {
        Queue<Integer> queue;

        public RecentCounter() {
            queue = new ArrayDeque<Integer>();
        }

        public int ping(int t) {
            queue.offer(t);
            while (queue.peek() < t - 3000) {
                queue.poll();
            }
            return queue.size();
        }
    }

    public static void main(String[] args) {

    }
}
